1906F - Maximize The Value - CodeForces Solution

#include <bits/stdc++.h>
#define endl '\n'
#define len(a) (int)a.size()
#define all(a) a.begin(), a.end()
#define allr(a) a.rbegin(), a.rend()

using namespace std;
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
const ll INF = 1e18 + 1e7;
const ll MOD = 1000000007;
const ld EPS = 1e-13;
const int MAXI = 1e9 + 1e7;

struct Node {
    ll max_pref = 0, max_suf = 0, max_subsegment = 0, sum = 0, max_element = 0;
};

const int MAXN = 100010;
Node t[4 * MAXN];

Node recalc(Node l, Node r) {
    Node res;
    res.sum = l.sum + r.sum;
    res.max_pref = max(l.max_pref, l.sum + r.max_pref);
    res.max_suf = max(r.max_suf, r.sum + l.max_suf);
    res.max_subsegment = max(l.max_suf + r.max_pref,
                             max(l.max_subsegment, r.max_subsegment));
    res.max_element = max(l.max_element, r.max_element);
    return res;
}

void update(int u, int l, int r, int pos, int val) {
    if (l == r) {
        t[u].max_pref = t[u].max_suf = t[u].max_subsegment = max(0, val);
        t[u].sum = t[u].max_element = val;
    } else {
        int mid = (l + r) / 2;
        if (pos <= mid)
            update(u * 2 + 1, l, mid, pos, val);
        else
            update(u * 2 + 2, mid + 1, r, pos, val);
        t[u] = recalc(t[u * 2 + 1], t[u * 2 + 2]);
    }
}
void update(int pos, int val) {
    update(0, 0, MAXN - 1, pos, val);
}
Node get_max_subsegment(int u, int l, int r, int ql, int qr) {
    if (ql <= l && r <= qr)
        return t[u];
    int mid = (l + r) / 2;
    if (ql <= mid && qr > mid) {
        return recalc(get_max_subsegment(u * 2 + 1, l, mid, ql, qr), get_max_subsegment(u * 2 + 2, mid + 1, r, ql, qr));
    } else if (ql <= mid)
        return get_max_subsegment(u * 2 + 1, l, mid, ql, qr);
    else
        return get_max_subsegment(u * 2 + 2, mid + 1, r, ql, qr);
}
ll get_max_subsegment(int ql, int qr) {
    Node res = get_max_subsegment(0, 0, MAXN - 1, ql, qr);
    return res.max_element <= 0 ? res.max_element : res.max_subsegment;
}

int32_t main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
#ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#endif
    int n, m;
    cin >> n >> m;
    vector<pair<int, int> > lseg[n], rseg[n];
    for (int i = 0; i < m; i++) {
        int l, r, x;
        cin >> l >> r >> x;
        lseg[l - 1].emplace_back(i, x);
        rseg[r - 1].emplace_back(i, x);
    }
    vector<tuple<int, int, int> > queries[n];
    int q;
    cin >> q;
    for (int i = 0; i < q; i++) {
        int k, l, r;
        cin >> k >> l >> r;
        queries[k - 1].emplace_back(i, l - 1, r - 1);
    }
    vector<ll> ans(q);
    for (int i = 0; i < n; i++) {
        for (auto [pos, val] : lseg[i])
            update(pos, val);
        for (auto [idx, ql, qr] : queries[i])
            ans[idx] = get_max_subsegment(ql, qr);
        for (auto [pos, val] : rseg[i])
            update(pos, 0);
    }
    for (int i = 0; i < q; i++)
        cout << ans[i] << endl;
}